The present invention relates to a method and apparatus for taking, for example, moving image data as an input for playback on a TV monitor or for recording on a recording medium, and further relates to method and apparatus for performing frequency conversion on image data, audio data, etc.
With increasing performance of personal computers, there on personal computers. When handling moving images on a personal computer, an apparatus such as a digital VTR for inputting moving images to the personal computer is connected, and moving image data pre recorded on a video tape or the like is input to the personal computer via the apparatus. The input moving image data is processed in various ways such as display on the screen of the personal computer and recording on a hard disk.
On the other hand, when playing back moving image data with audio on a personal computer, sample data conversion for converting the frequency of video and audio of digital format may become necessary because of the constraints of the hardware constituting the personal computer and other software.
In the prior art, when performing sample rate conversion, it is common practice to first upsample the input digital data and then apply low-pass filtering to decimate the data according to the output sample rate.
A sample data conversion method according to the prior art will be described below with reference to FIG. 17.
FIG. 17 is a diagram for explaining one example of sample data conversion according to the prior art.
The example of FIG. 17 shows sample data sequence conversion in the case where an input sample data sequence X[i] consisting of 400 samples is converted into an output sample data sequence Y[j] consisting of 300 samples. In this example, data X[i] represents, for example, the actual pixel value of the input image before the conversion, while Y[j] represents the pixel value of the output image after the conversion. In this case, i and j are variables each corresponding to the position coordinates of a pixel in the horizontal direction on a line it a frame.
First, a data sequence Z[k] upsampled from the input sample data sequence X[i] is obtained. When performing the upsampling, interpolation must be applied to the input sample data sequence X[i] so that all sample values Y[j] in the output sample data sequence Y[j after the conversion will be contained in the data sequence Z[k]. Accordingly, the number of samples in the upsampled data sequence Z[k] is the least common multiple of the number of samples in the input sample data sequence X[i] and the number of samples in the output sample data sequence Y[j]. That is, it is the least common multiple of the number of samples before the conversion and the number of samples after the conversion. In the illustrated example, the number of samples in the upsampled data sequence Z[k] is 1,200 which is the least common multiple of 400 and 300.
Then, after low-pass filtering the upsampled data sequence Z[k] to eliminate distortion due to aliasing, unnecessary samples are decimated to obtain the output sample data sequence Y[j]. In the example of FIG. 17, the output sample data sequence Y[j] can be obtained by selecting, for example, a first sample in the upsampled data sequence Z[k], and then selecting every fourth sample from the first sample.
The above-described method is disclosed, for example, in Japanese Laid-open Patent No. 10-164468.
In the above method, when obtaining each sample in the upsampled data sequence Z[k], there frequently occur calculations for obtaining the value of a sample between two adjacent samples X[i] and X[i+1] in the input sample data sequence X[i] by weighted averaging based on the ratio between the distance from X[i] and the distance from X[i+1], i.e., (1xe2x88x92w):w (0xe2x89xa6wxe2x89xa61). When obtaining a number AX existing at a designated position between two numbers A1 and A2 by using the ratio of the distances from A1 and A2 as described above, if the following (equation 12) holds, the value of the number AX is expressed by (equation 13) shown below.
(Distance between numbers A1 and AX):(Distance between numbers AX and A2)=(1xe2x88x92w):wxe2x80x83xe2x80x83(Equation 12)
where 0xe2x89xa6wxe2x89xa61
AX=wxc3x97A1+(1xe2x88x92w)xc3x97A2xe2x80x83xe2x80x83(Equation 13)
When obtaining a number AX lying between two adjacent numbers A1 and A2 by a computer as described above, the method based on the flow chart of FIG. 18 is usually employed.
In FIG. 18, 1801 is a first load step, 1802 is a second load step, 1803 is a third load step, 1804 is a fourth load step, 1805 is a first multiplication step, 1806 is a subtraction step, 1807 is a second multiplication step, 1808 is an addition step, and 1809 is an output step.
The operation of the flow chart of FIG. 18 will be described below.
The two input sample values A1 and A2 and parameter w are loaded into a register A, a register B, and a register C in the first load step 1801, the second load step 1802, and the third load step 1803, respectively, and a numeric value 1 is loaded into a register D in the fourth load step 1804.
Next, in the first multiplication step 1805, the contents of the register A is multiplied by the contents of the register C. After the multiplication, (wxc3x97A1) is held in the register A.
In the subtraction step 1806, the contents of the register C is subtracted from the contents of the register D. After the subtraction, (1xe2x88x92w) is held in the register D.
In the second multiplication step 1807, the contents of the register B is multiplied by the contents of the register D. After the multiplication, (1xe2x88x92w)xc3x97A2 is held in the register B.
In the addition step 1808, the contents of the register B is added to the contents of the register A. After the addition, (Wxc3x97A1+(1xe2x88x92w)xc3x97A2) is held in the register A.
Finally, in the output step 1809, AX, that is, (wxc3x97A1+(1xe2x88x92w)xc3x97A2), is output.
In this example, the operations necessary to obtain one number AX are four load operations, two multiplication operations, a subtraction, and an addition.
With recent advances in computer technology, it has become possible to accomplish the above-described sample data conversion at relatively high speed not only by dedicated hardware but also by personal computers (PCs).
However, in the above prior art which is directed to the processing of moving image data that does not have a real time requirement, the following problem occurs (1) if the PC does not have sufficient performance for handling moving images or, (2) even if the PC has sufficient performance as mentioned above, when interrupt processing occurs during moving image processing, though in the latter case there will be no problem when the PC processes only moving image data.
That is, since the amount of moving image data is very large, there can occur cases where the processing of the input moving image data for playback or for recording on a recording medium such as a hard disk cannot be completed in time, and in such cases, processing of part of the data has had to be given up. This has lead to the problem that when recording moving images on a hard disk, part of a scene is dropped or the recording of image data itself is stopped.
Furthermore, in the sample number conversion of the above-mentioned prior art, when performing the upsampling, data must be interpolated so that all samples after the conversion will be contained.
As a result, the number of samples in the upsampled data sequence is the least common multiple of the number of samples before the conversion and the number of samples after the conversion.
However, even when the number of samples before the conversion, M, and the number of samples after the conversion, N, are both small, if M and N are natural numbers relatively prime to each other, the number of samples in the upsampled data sequence is Mxc3x97N, which can become a large number depending on the case. In that case, a memory having a very large capacity is needed in order to hold the upsampled data sequence.
Furthermore, in that case, the upsampling requires an enormous number of multiplications and subtractions, which means that an enormous amount of computation is required to accomplish the upsampling. This also means an enormous amount of computation for decimation including low-pass filtering.
Since such an enormous amount of computation becomes necessary, an enormous amount of time for computation is required. This can become a fatal shortcoming in processing video signals or audio signals when real time processing is required.
It is an object of the present invention to provide a data processing method and a data processing apparatus that can reduce data dropping, compared with the prior art, during playback or recording of moving image data when moving images prerecorded on a recording medium or the like and having no real time requirement are input to a conventional personal computer for processing.
Further, as described above, the prior art has had the problem that a large capacity memory and an enormous amount of computation are required when converting an input digital signal consisting of an arbitrary number of samples into an output digital signal consisting of an arbitrary number of samples that is different from the number of samples in the input digital signal; in view of this problem, it is another object of the present invention to provide a data processing method and a data processing apparatus that can accomplish the conversion with a small memory capacity and a small amount of computation when converting an input digital signal consisting of an arbitrary number of samples into an output digital signal consisting of an arbitrary number of samples that is different from the number of samples forming the input digital signal.
A 1st invention of the present invention is a data processing method for processing moving image data by reading and inputting said moving image data from another recording medium, comprising:
a moving image input step for inputting said moving image data for each prescribed unit;
a position information input step for inputting information concerning a position at which said prescribed unit of moving image data is recorded on said recording medium;
a moving image processing step for processing said moving image for each said prescribed unit;
a discontinuity point storing step for storing position information concerning a location of the processing unit of last moving image data that has successfully been processed without interruption, or a position preceding said location, as a discontinuity point when there occurs moving image data that cannot be processed in said moving image processing step;
a re-input step for rereading and re-inputting previously readout moving image data and position information by controlling said recording medium; and
a processing resuming step for detecting position information that matches the position information of said discontinuity point from among the position information input in said re-input step, and for resuming said moving image processing by using said detected position information.
A 2nd invention of the present invention is a data processing apparatus for processing moving image data by reading and inputting said moving image data from another recording medium, comprising:
moving image input means for inputting said moving image data for each prescribed unit;
position information input means for inputting information concerning a position at which said prescribed unit of moving image data is recorded on said recording medium;
moving image processing means for processing said moving image for each said prescribed unit;
discontinuity point storing means for storing position information concerning a location of the processing unit of last moving image data that has successfully been processed without interruption, or a position preceding said location, as a discontinuity point when there occurs moving image data that cannot be processed by said moving image processing means;
re-input means for rereading and re-inputting previously readout moving image data and position information by controlling said recording medium; and
processing resuming means for detecting position information that matches the position information of said discontinuity point from among the position information input by said re-input means, and for resuming said moving image processing by using said detected position information.
A 3rd invention of the present invention is a data processing method according to said 1st invention, wherein said another recording medium is a video tape, and
said information concerning said position is information concerning a record time counted from a prescribed position on said video tape.
A 4th invention of the present invention is a data processing apparatus according to said 2nd invention, wherein said another recording medium is a video tape, and
said information concerning said position is information concerning a record time counted from a prescribed position on said video tape.
A 5th invention of the present invention is a data processing method for processing moving image data by reading and inputting said moving image data from another recording medium, comprising:
a moving image input step for inputting said moving image data for each prescribed unit;
a recorded time information input step for inputting information concerning time at which said prescribed unit of moving image data was recorded on said recording medium;
a moving image processing step for processing said moving image for each said prescribed unit;
a discontinuity point storing step for storing recorded time information concerning a location of the processing unit of last moving image data that has successfully been processed without interruption, or a position preceding said location, as a discontinuity point when there occurs moving image data that cannot be processed in said moving image processing step;
a re-input step for rereading and re-inputting previously readout moving image data and recorded time information by controlling said recording medium; and
a processing resuming step for detecting recorded time information that matches the recorded time information of said discontinuity point from among the recorded time information input in said re-input step, and for resuming said moving image processing by using said detected recorded time information.
A 6th invention of the present invention is a data processing apparatus for processing moving image data by reading. and inputting said moving image data from another recording medium, comprising:
moving image input means for inputting said moving image data for each prescribed unit;
recorded time information input means for inputting information concerning the time at which said prescribed unit of moving image data was recorded on said recording medium;
moving image processing means for processing said moving image for each said prescribed unit;
discontinuity point storing means for storing recorded time information concerning a location of the processing unit of last moving image data that has successfully been processed without interruption, or a position preceding said location, as a discontinuity point when there occurs moving image data that cannot be processed by said moving image processing means;
re-input means for rereading and re-inputting previously readout moving image data and recorded time information by controlling said recording medium; and
processing resuming means for detecting recorded time information that matches the recorded time information of said discontinuity point from among the recorded time information input by said re-input means, and for resuming said moving image processing by using said detected recorded time information.
A 7th invention of the present invention is a data processing method for inputting and processing moving image data, comprising:
a moving image input step for inputting said moving image data for each prescribed unit;
a playback time information input step for inputting information concerning time at which said moving image data is to be played back for each said prescribed unit;
a moving image processing step for processing said moving image for each said prescribed unit;
a discontinuity point storing step for storing playback time information concerning the location of the processing unit of last moving image data that has successfully been processed without interruption, or a position preceding said location, as a discontinuity point when there occurs moving image data that cannot be processed in said moving image processing step;
a re-input step for re inputting said moving image data and said playback time information; and
a processing resuming step for detecting playback time information that matches the playback time information of said discontinuity point from among the playback time information input in said re-input step, and for resuming said moving image processing by using said detected playback time information.
An 8th invention of the present invention is a data processing apparatus for inputting and processing moving image data, comprising:
moving image input means for inputting said moving image data for each prescribed unit;
playback time information input means for inputting information concerning time at which said moving image data is to be played back for each said prescribed unit;
moving image processing means for processing said moving image for each said prescribed unit;
discontinuity point storing means for storing playback time information concerning the location of the processing unit of last moving image data that has successfully been processed without interruption, or a position preceding said location, as a discontinuity point when there occurs moving image data that cannot be processed by said moving image processing means;
re-input means for re-inputting said moving image data and said playback time information; and
processing resuming means for detecting playback time information that matches the playback time information of said discontinuity point from among the playback time information input by said re-input means, and for resuming said moving image processing by using said detected playback time information.
A 9th invention of the present invention is a data processing method according to said 1st, 5th, or 7th invention, wherein when performing said moving image processing by temporarily storing said moving image data in a buffer, said discontinuity point storing step detects a condition in which new moving image data is input into an area of said buffer, the processing of moving image data in said area is not yet finished.
A 10th invention of the present invention is a data processing apparatus according to said 2nd, 6th, or 8th invention, wherein when performing said moving image processing by temporarily storing said moving image data in a buffer, said discontinuity point storing means detects a condition in which new moving image data is input into an area of said buffer, the processing of moving image data in said area is not yet finished.
An 11th invention of the present invention is a data processing method according to said 1st, 5th, or 7th invention, wherein said another recording medium is a video tape, and in said re-input step, when performing said moving image data playing back, said moving image data is played back once again after rewinding said video tape to a desired playback position.
A 12th invention of the present invention is a data processing apparatus according to said 2nd, 6th, or 8th invention, wherein said another recording medium is a video tape, and when performing said moving image data playing back, said re-input means plays back said moving image data once again after rewinding said video tape to a desired playback position.
A 13th invention of the present invention is a data processing method for taking as an input a moving image consisting of N input frames per prescribed time, and for processing M frames per said prescribed time, comprising:
a register value initializing step for setting an initial value in a designated register;
a register value addition step for adding a constant m (where m=M or m=xe2x88x92M) to said register value when said input frame is input; and
an input frame processing step for (1) subtracting N from said register value and processing said input frame when said register value is not smaller than a prescribed value T as a result of said register value addition step in the case of said constant m=M, or (2) adding N to said register value and processing said input frame when said register value is not larger than said prescribed value T as a result of said register value addition step in the case of said constant m=xe2x88x92M
A 14th invention of the present invention is a data processing apparatus for taking as an input a moving image consisting of N input frames per prescribed time, and for processing M frames per said prescribed time, comprising:
register value initializing means for setting an initial value in a designated register;
register value adding means for adding a constant m (where m=M or m=xe2x88x92M) to said register value when said input frame is input; and
input frame processing means for (1) subtracting N from said register value and processing said input frame when said register value is not smaller than a prescribed value T as a result of the addition by said register value adding means in the case of said constant m=M, or (2) adding N to said register value and processing said input frame when said register value is not larger than said prescribed value T as a result of the addition by said register value adding means in the case of said constant m=xe2x88x92M.
A 15th invention of the present invention is a data processing method for taking as an input a moving image consisting of N input frames per prescribed time, and for processing M frames per said prescribed time, comprising:
a register value initializing step for setting an initial value not larger than N in a designated register;
a first frame processing step for processing first input frame when said first input frame is input;
a register value addition step for adding a constant m (where m=M or m=xe2x88x92M) to said register value when said input frame other than said first input frame is input; and
an input frame processing step for (1) subtracting N from said register value and processing said input frame when said register value is not smaller than a prescribed value T as a result of said register value addition step in the case of said constant m=M, or (2) adding N to said register value and processing said input frame when said register value is not larger than said prescribed value T as a result of said register value adding means [sic; step] in the case of said constant m=xe2x88x92M.
A 16th invention of the present invention is a data processing apparatus for taking as an input a moving image consisting of N input frames per prescribed time, and for processing M frames per said prescribed time, comprising:
register value initializing means for setting an initial value not larger than N in a designated register;
first frame processing means for processing first input frame when said first input frame is input;
register value adding means for adding a constant m (where m=M or m=xe2x88x92M) to said register value when said input frame other than said first input frame is input; and
input frame processing means for (1) subtracting N from said register value and processing said input frame when said register value is not smaller than a prescribed value T as a result of the addition by said register value adding means in the case of said constant m=M, or (2) adding N to said register value and processing said input frame when said register value is not larger than said prescribed value T as a result of the addition by said register value adding means in the case of said constant m=xe2x88x92M.
A 17th invention of the present invention is a data processing method for taking as an input a moving image consisting of N input frames per prescribed time, and for processing M frames per said prescribed time, comprising:
a number-of-processing-frames initializing step for setting an initial value M representing the number of M frames;
a register value initializing step for setting an initial value not larger than N in a designated register;
a register value addition step for adding a constant m (where m=M or m=xe2x88x92M) to said register value when said input frame is input;
an input frame processing step for (1) subtracting N from said register value and processing said input frame when said register value is not smaller than a prescribed value T as a result of said register value addition step in the case of said constant m=M, or (2) adding N to said register value and processing said input frame when said register value is not larger than said prescribed value T as a result of said register value addition step in the case of said constant m=xe2x88x92M; and
a number-of-processing-frames adjusting step for varying said number of processing frames, M, and said constant m in accordance with the degree of load in said input frame processing step.
An 18th invention of the present invention is a data processing apparatus for taking as an input a moving image consisting of N input frames per prescribed time, and for processing M frames per said prescribed time, comprising:
number-of-processing-frames initializing means for setting an initial value M representing the number of M frames;
register value initializing means for setting an initial value not larger than N in a designated register;
register value adding means for adding a constant m (where m=M or m=xe2x88x92M) to said register value when said input frame is input;
input frame processing means for (1) subtracting N from said register value and processing said input frame when said register value is not smaller than a prescribed value T as a result of the addition by said register value adding means in the case of said constant m=M, or (2) adding N to said register value and processing said input frame when said register value is not larger than said prescribed value T as a result of the addition by said register value adding means in the case of said constant m=xe2x88x92M; and
number-of-processing-frames adjusting means for varying said number of processing frames, M, and said constant m in accordance with the degree of load in said input frame processing means.
A 19th invention of the present invention is a data processing method according to said 13th, 15th, or 17th invention wherein in the case of said constant m=M, T=N or T=N+1 is set as said prescribed value T, while in the case of said constant m=xe2x88x92M, T=0 or T=xe2x88x921 is set as said prescribed value T.
A 20th invention of the present invention is a data processing apparatus according to said 14th, 16th, or 18th invention wherein in the case of said constant m=M, T=N or T=N+1 is set as said prescribed value T, while in the case of said constant m=xe2x88x92M, T=0 or T=xe2x88x921 is set as said prescribed value T.
A 21st invention of the present invention is a data processing method according to said 17th invention, wherein when performing moving image processing by temporarily storing moving image data in a buffer,
in said number-of-processing-frames adjusting step, (1) said number of processing frames is reduced when the amount of moving image data remaining unprocessed in said buffer shows a tendency to increase, and (2) said number of processing frames is increased when the amount of moving image data remaining unprocessed in said buffer shows a tendency to decrease.
A 22nd invention of the present invention is a data processing apparatus according to said 18th invention, wherein when performing moving image processing by temporarily storing moving image data in a buffer,
said number-of-processing-frames adjusting means (1) reduces said number of processing frames when the amount of moving image data remaining unprocessed in said buffer shows a tendency to increase, and (2) increases said number of processing frames when the amount of moving image data remaining unprocessed in said buffer shows a tendency to decrease.
A 23rd invention of the present invention is a data processing method according to said 17th invention, wherein when performing moving image processing by temporarily storing moving image data in a buffet, only moving image data to be actually processed is stored in said buffer.
A 24th invention of the present invention is a data processing apparatus according to said 18th invention, wherein when performing moving image processing by temporarily storing moving image data in a buffer, only moving image data to be actually processed is stored in said buffer.
A 25th invention of the present invention is a data processing method for converting an input sample data sequence consisting of M samples to an output sample data sequence consisting of N samples, comprising:
an initial value setting step for setting a nonzero constant k and a prescribed parameter W;
a sequential addition step for repeating an operation to add k*N to said parameter W by sequentially scanning input sample data as long as Wxe2x89xa60 when k greater than 0 or as long as Wxe2x89xa70 when k less than 0;
a sample data output step for outputting said converted output sample data when W becomes larger than 0 in the case of k greater than 0 or W becomes smaller than 0 in the case of k greater than 0 in said sequential addition step; and
a subtraction step for subtracting k*M from said W, wherein
said sequential addition step, said sample data output step, and said subtraction step are repeated until said N output sample data have been output.
A 26th invention of the present invention is a data processing method according to said 25th invention, wherein when each sample data in said output sample data sequence has a byte length represented by a prescribed constant b, and an overall byte length of said output sample data sequence is not an integral multiple of a prescribed constant p, there is further included a dummy adding step for adding dummy data of Lxe2x88x92b*N bytes at end of said output sample data sequence of N samples, where L is a multiple of p not smaller than b*N, and
said output sample data sequence of N samples is output together with said dummy data.
A 27th invention of the present invention is a data processing method according to said 25th invention, wherein said k is 1.
A 28th invention of the present invention is a data processing method according to said 25th invention, wherein said k is the reciprocal of the greatest common measure of said M and said N.
A 29th invention of the present invention is a data processing method comprising:
a data input step for inputting data of two predetermined numbers X1 and X2;
a parameter input step for inputting a parameter w for obtaining a number Y located at a position at which the distance between said X1 and said X2 is divided in a ratio of (1xe2x88x92w):w;
a subtraction step for generating X3 by subtracting said X2 from said X;
a times w multiplying step for generating X4 by multiplying the X3 obtained in said subtraction step by said parameter w;
an addition step for generating Y by adding said X2 to the X4 obtained in said times w multiplying step; and
an output step for outputting said Y obtained in said addition step.
A 30th invention of the present invention is a data processing method for inputting N data sequences X[i] [sic; for inputting data sequence X[i] including N data], and for outputting as Y[i] a value obtained by dividing said X[i] by a constant Q, comprising:
an initializing step for obtaining a coefficient w=2{circumflex over ( )}k/Q (where {circumflex over ( )}k means raising to the power k) for an integer k larger than 0;
a times w multiplying step for obtaining w*X[i] using said X[i] and said coefficient w obtained in said initializing step, and for taking said obtained w*X[i] as a new X[i]; and
a bit shift step for taking as Y[i] a value obtained by shifting the X[i] obtained in said times w multiplying step by kbits in a low order bit direction when said X[i] is expressed in bit representation, wherein
said times w multiplying step and said bit shift step are repeated N times to sequentially output N data sequences Y[i] [sic; to sequentially output data sequence Y[i] including N data].
A 31st invention of the present invention is a data processing apparatus for converting an input sample data sequence consisting of M samples to an output sample data sequence consisting of N samples, comprising:
initial value setting means for setting a nonzero constant k and a prescribed parameter W;
sequential adding means for repeating an operation to add k*N to said parameter W by sequentially scanning input sample data as long as Wxe2x89xa60 when k greater than 0 or as long as Wxe2x89xa70 when k less than 0;
sample data output means for outputting said converted output sample data when W becomes larger than 0 in the case of k greater than 0 or W becomes smaller than 0 in the case of k less than 0 by said sequential adding means; and
subtracting means for subtracting k*M from said W, wherein
said sequential adding means, said sample data output means, and said subtracting means are operated in sequence repeatedly until said N output sample data have been output.
A 32nd invention of the present invention is a data processing apparatus according to said 31st invention, wherein when each sample data in said output sample data sequence has a byte length represented by a prescribed constant b, and an overall byte length of said output sample data sequence is not an integral multiple of a prescribed constant p, there is further included a dummy adding means for adding dummy data of Lxe2x88x92b*N bytes at end of said output sample data sequence of N samples, where L is a multiple of p not smaller than b*N, and
said output sample data sequence of N samples is output together with said dummy data.
A 33rd invention of the present invention is a data processing apparatus according to said 31st invention, wherein said k is 1.
A 34th invention of the present invention is a data processing apparatus according to said 31st invention, wherein said k is the reciprocal of the greatest common measure of said M and said N.
A 35th invention of the present invention is a data processing apparatus comprising:
data input means for inputting data of two predetermined numbers X1 and X2;
parameter input means for inputting a parameter w for obtaining a number Y located at a position at which the distance between said X1 and said X2 is divided in a ratio of (1xe2x88x92w):w;
subtracting means for generating X3 by subtracting said X2 from said X1;
times w multiplying means for generating X4 by multiplying the X3 obtained by said subtracting means by said parameter w;
adding means for generating Y by adding said X2 to the X4 obtained by said times w multiplying means; and
output means for outputting said Y obtained by said adding means.
A 36th of the present invention is a data processing apparatus for inputting N data sequences X[i] [sic; for inputting data sequence X[i] including N data], and for outputting as Y[i] a value obtained by dividing said X[i] by a constant Q, comprising:
initializing means for obtaining a coefficient w=2{circumflex over ( )}k/Q (where {circumflex over ( )}k means raising to the power k) for an integer k larger than 0;
times w multiplying means for obtaining w*X[i] using said X[i] and said coefficient w obtained by said initializing means, and for taking said obtained w*X[i] as a new X[i]; and
bit shift means for taking as Y[i] a value obtained by shifting the X[i] obtained by said times w multiplying means by k bits in a low order bit direction when said X[i] is expressed in bit representation, wherein
said times w multiplying means and said bit shift means are operated in sequence N times to sequentially output N data sequences Y[i] [sic; to sequentially output data sequence Y[i] including N data].
A 37th invention of the present invention is a program recording medium having recorded thereon a program for enabling a computer to carry out all or part of operations in all or part of the steps of a data processing method as described in any one of said 1st, 3rd, 5th, 7th, 9th, 11th, 13th, 15th, 17th, 19th, 21st, 23rd, and 25th to 30th inventions.
A 38th invention of the present invention is a program recording medium having recorded thereon a program for enabling a computer to implement all or part of the functions of all or part of the means in a data processing apparatus as described in any one of said 2nd, 4th, 6th, 8th, 10th, 12th, 14th, 16th, 18th, 20th, 22nd, 24th, and 31st to 36th inventions.